二分图

一.二分图的基本知识

1.二分图的概念

       ~~~~~~~二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集,则称图G为一个二分图。我们一般把其中一部分称为x部,另一部分称为y部。


2.二分图的判定

1.在图中找一个点为起点 ,将它的邻接点标号为2,再将标号为2的点的邻接点标号为3,以此类推。注意,如果该点已经标号,则不进行操作。

  1. 显然,标号为奇数的点和编号为偶数的点各在x部,y部,我们把它放在一起。如图:

3.我们判断每一条边,如果所有边其中一端在x部,另一端在y部,那么它就是一个二分图。显然,上图不是一个二分图。


3.二分图的性质

       ~~~~~~~若无向图G为二分图,则G至少有两个顶点,且其所有回路的长度均为偶数。


4.二分图匹配与最大匹配

       ~~~~~~~给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。如图,图中黄色线段是该图的一个匹配

在所有二分图匹配中,边数最多的匹配称为二分图的最大匹配,如图:

另外,

  • 如果一个匹配中,图中的每个顶点都和匹配中某条边相关联,则称此匹配为完美匹配。
  • 如果一个最大匹配M覆盖了X部或者Y部中的所有点,则成为完备匹配。如果覆盖了X部的所有点,则称X部到Y部的完备匹配,而如果覆盖了Y部的所有点,则称Y部到X部的完备匹配。而如果同时覆盖了X部和Y部的所有点,则它就是完美匹配。
  • 由上述两条定义,我们可以得到:完备匹配包含了完美匹配

5.增广路径

       ~~~~~~~M是图G的一个匹配,若P是图G中一条连通两个未匹配顶点的路径,并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。如图:(黄色为已匹配线段,蓝色为未匹配线段,高亮部分便是一条增广路径)

由增广路的定义可以推出下述结论:

  1. 因为第一条边和最后一条边都不属于M,所以P的路径长度必定为奇数。
  2. 不断寻找增广路可以得到一个更大的匹配M’,直到找不到更多的增广路。
  3. M为G的最大匹配当且仅当不存在M的增广路径。

那么,如何找一条增广路径呢?我们可以用dfs实现


二.二分图的最大匹配问题

1.匈牙利算法

匈牙利算法,由匈牙利数学家Edmonds于1965年提出。

       ~~~~~~~算法的思路:如果该图有一条增广路径,那么我们进行取反操作(将匹配的变为未匹配的,将未匹配的变为匹配的),就可以得到更大的一组匹配。重复该操作,直至找不到增广路径,便得到了最大匹配。
       ~~~~~~~找增广路径的算法前面已经讲过,只需从每一个顶点出发寻找增广路即可。如果找到了,就将最大匹配数加一。

代码如下(邻接表):

//fx[],fy[]分别代表x部匹配的y部顶点,y部匹配的x部顶点
bool Augmented_path( int u ) {
    for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
        int v = Graph[ u ][ i ];
        if( !vis[ v ] ) {//如果该点未遍历
            vis[ v ] = 1;
            if( fy[ v ] == -1 || Augmented_path( fy[ v ] ) ) {//如果该点未匹配或以该点为起点有增广路径则找到了一条增广路径
                fx[ u ] = v , fy[ v ] = u;//两点互相匹配
                return 1;
            }
        }       
    }
    return 0;//找不到增广路径
}
int Hungary(  ) {
    int Ans = 0;
    memset( fx , -1 , sizeof( fx ) );
    memset( fy , -1 , sizeof( fy ) );
     
    for( int i = 1 ; i <= n ; i ++ ) {
        if( fx[ i ] == -1 ) {//如果该点未匹配,则以它为起点找增广路径
            memset( vis , 0 , sizeof( vis ) );
            Ans += Augmented_path( i );
        }
    }
    return Ans;
}

复杂度分析:

时间 空间
邻接矩阵 Θ(n3)\Theta(n^3) Θ(n2)\Theta(n^2)
邻接表 Θ(nm)\Theta(nm) Θ(n+m)\Theta(n+m)

3.例题

1. 洛谷 P1894 (完美的牛栏The Perfect Stall)

把奶牛看做x部,牛栏看做y部,将奶牛和它喜欢的牛栏连一条边,求该图的最大匹配即可。
代码如下:

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

int n,m,fx[ 205 ],fy[ 205 ];
bool vis[ 205 ];
vector< int > Graph[ 205 ];

bool Augmented_path( int u ) {	//求增广路经
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( !vis[ v ] ) {
			vis[ v ] = 1;
			if( fy[ v ] == -1 || Augmented_path( fy[ v ] ) ) {
				fx[ u ] = v , fy[ v ] = u;
				return 1;
			}
		}		
	}
	return 0;
}
int Hungary(  ) {	//匈牙利算法
	int Ans = 0;
	memset( fx , -1 , sizeof( fx ) );
	memset( fy , -1 , sizeof( fy ) );
	
	for( int i = 1 ; i <= n ; i ++ ) {
		if( fx[ i ] == -1 ) {
			memset( vis , 0 , sizeof( vis ) );
			Ans += Augmented_path( i );
		}
	}
	return Ans;
}
int main( ) {
	int x,y;
	scanf("%d %d",&n,&m);
	for( int i = 1 ; i <= n ; i ++ ) {
		scanf("%d",&x);
		for( int j = 1 ; j <= x ; j ++ ) {
			scanf("%d",&y);
			Graph[ i ].push_back( y );	//将奶牛和它喜欢的牛栏连一条边
		}
	}
	printf("%d",Hungary());
	return 0;
}
2. ZOJ P1002 (Fire Net)

如果在一个点放了一个碉堡,那么他的行列在没有墙的情况下就不能再放另个一个碉堡,那么我们不如把它的行看做一个部分,他的列看做一部分。每个行部分与每个列部分之间最多只能放一个碉堡,所以在每个行部分与每个列部分之间连一条边,求图的最小点覆盖(即用最少的点覆盖整个图)。
下面引入一个定理:图的最小点覆盖=图的最大匹配
用匈牙利算法求解最大匹配即可,代码如下:

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
  
int n,k,fx[ 405 ],fy[ 405 ];
bool vis[ 405 ],f[ 405 ][ 405 ];
vector< int > Graph[ 405 ];
  
bool Augmented_path( int u ) {
    for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
        int v = Graph[ u ][ i ];
        if( !vis[ v ] ) {
            vis[ v ] = 1;
            if( fy[ v ] == -1 || Augmented_path( fy[ v ] ) ) {
                fx[ u ] = v , fy[ v ] = u;
                return 1;
            }
        }       
    }
    return 0;
}
int Hungary(  ) {
    int Ans = 0;
    memset( fx , -1 , sizeof( fx ) );
    memset( fy , -1 , sizeof( fy ) );
      
    for( int i = 1 ; i <= k ; i ++ ) {
        if( fx[ i ] == -1 ) {
            memset( vis , 0 , sizeof( vis ) );
            Ans += Augmented_path( i );
        }
    }
    return Ans;
}
 
int a1[ 25 ][ 25 ],a2[ 25 ][ 25 ];
char s[ 25 ][ 25 ];
void Init( ) {
    k = 1;
    for( int i = 1 ; i <= n ; i ++ ) {	//将行相连的置为一个部分	
        for( int j = 1 ; j <= n ; j ++ ) {
            if( s[ i ][ j ] == 'X' ) {
                if( s[ i ][ j - 1 ] == '.' )
                    k ++;
            }   
            else
                a1[ i ][ j ] = k;
        }
        k ++;
    }
    k = 1;
    for( int i = 1 ; i <= n ; i ++ ) {	//将列相连的置为一个部分
        for( int j = 1 ; j <= n ; j ++ ) {
            if( s[ j ][ i ] == 'X' ) {
                if( s[ j - 1 ][ i ] == '.' )
                    k ++;
            }   
            else
                a2[ j ][ i ] = k;
        }
        k ++;
    }
 
    for( int i = 1 ; i <= n ; i ++ )	//将不同的行列部分之间连边
        for( int j = 1 ; j <= n ; j ++ )
            if( !f[ a1[ i ][ j ] ][ a2[ i ][ j ] ] && a1[ i ][ j ] && a2[ i ][ j ] ) {
                f[ a1[ i ][ j ] ][ a2[ i ][ j ] ] = 1;
                Graph[ a1[ i ][ j ] ].push_back( a2[ i ][ j ] );
            }
}
int main( ) {
    scanf("%d",&n);
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= n ; j ++ )
            cin >> s[ i ][ j ];
         
    Init( );
    printf("%d",Hungary());
    return 0;
}